package com.Oct_Thirteen;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 面试题 08.08. 有重复字符串的排列组合
 * 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
 * https://leetcode.cn/problems/permutation-ii-lcci/
 *
 * 2022/10/14 00:08
 */

public class Solution08_08 {

    List<String> list=new ArrayList<>();

    public String[] permutation(String S) {
        boolean[] visited;
        char[] c=S.toCharArray();
        Arrays.sort(c);
        visited=new boolean[S.length()];
        //Arrays.fill(visited,false);
        dfs(c,new StringBuilder(),visited);
        String[] ans=new String[list.size()];
        for (int i=0;i<list.size();i++)
        {
            ans[i]=list.get(i);
        }
        //System.out.println(ans.length);
        return ans;
    }

    void dfs(char[] s, StringBuilder path, boolean[] visited){
        if (path.length()==s.length)
        {
            list.add(path.toString());
            return;
        }
        for (int i=0;i<s.length;i++)
        {
            if (i>0&&s[i]==s[i-1]&&!visited[i-1]) continue;
            if (!visited[i]){
                    visited[i] = true;
                    path.append(s[i]);
                    dfs(s, path, visited);
                    path.deleteCharAt(path.length()-1);
                    visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution08_08 solution08_08=new Solution08_08();
        System.out.println(Arrays.toString(solution08_08.permutation("qqe")));
    }

}
